// Copyright (c) Huawei Technologies Co., Ltd. 2025. All rights reserved.
// This source file is part of the Cangjie project, licensed under Apache-2.0
// with Runtime Library Exception.
//
// See https://cangjie-lang.cn/pages/LICENSE for license information.

#include "llvm/Analysis/CallGraph.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Transforms/Utils/Cloning.h"

#include "Base/CGTypes/CGType.h"
#include "DIBuilder.h"
#include "IRAttribute.h"
#include "IRBuilder.h"
#include "Utils/BlockScopeImpl.h"
#include "Utils/CGUtils.h"
#include "cangjie/CHIR/Value.h"
#include "cangjie/Utils/ProfileRecorder.h"

namespace Cangjie::CodeGen {

llvm::Value* GenerateMainRetVal(IRBuilder2& irBuilder, llvm::Value* userMainRetVal);
namespace {
void CreatePrintStackTraceCall(IRBuilder2& irBuilder, llvm::Value* exceptionValue)
{
    const std::string errorClassName = "_CNat5ErrorE";
    const std::string printStackTraceIdent = "printStackTrace";
    const std::string printStackTraceFuncName = "_CNat5Error15printStackTraceHv";

    auto& cgMod = irBuilder.GetCGModule();
    auto& cgCtx = irBuilder.GetCGContext();
    auto printStackTraceFuncNode = cgCtx.GetImplicitUsedFunc(printStackTraceFuncName);
    auto printStackTraceFuncType = static_cast<CHIR::FuncType*>(printStackTraceFuncNode->GetType());
    // For now:
    auto exceptionTi = irBuilder.GetTypeInfoFromObject(exceptionValue);
    // Get the func ptr of `printStackTrace`
    // `printStackTrace` is the 3rd virtual method defined in `class Error`
    auto idxOfError = irBuilder.getInt64(0U);
    auto idxOfPrintStackTrace = irBuilder.getInt64(2U);
    auto funcInt8Ptr = irBuilder.CallIntrinsicGetVTableFunc(exceptionTi, idxOfError, idxOfPrintStackTrace);
    auto meta =
        llvm::MDTuple::get(cgCtx.GetLLVMContext(), llvm::MDString::get(cgCtx.GetLLVMContext(), "std.core:Error"));
    funcInt8Ptr->setMetadata("IntroType", meta);
    auto concreteFuncType = static_cast<CGFunctionType*>(CGType::GetOrCreate(cgMod, printStackTraceFuncType));
    auto funcPtr =
        irBuilder.LLVMIRBuilder2::CreateBitCast(funcInt8Ptr, concreteFuncType->GetLLVMFunctionType()->getPointerTo());
    auto paramCGType = CGType::GetOrCreate(cgMod, printStackTraceFuncType->GetParamTypes()[0]);
    CGValue paramCGValue(exceptionValue, paramCGType);
    irBuilder.CreateCallOrInvoke(*concreteFuncType, funcPtr, {&paramCGValue});
}

/*
 * @brief The IR layout generated by CreateUnwindBlockForTryCatchWrapper is as follows:
 *   ...
 *   invoke xxx_function()
 *     to label %normalDest unwind label %unwindDest
 *
 * normalDest:                                  ; preds = %invoke.continue
 *   ...
 *
 * unwindDest:                                  ; preds = %invoke.continue
 *   %0 = landingpad token
 *          catch i8* null
 *   %1 = call i8* @llvm.cj.get.exception.wrapper()
 *   %2 = call i8 addrspace(1)* @llvm.cj.begin.catch(i8* %1)
 *   %3 = call i1 @llvm.cj.is.instance.of(i8 addrspace(1)* %2, i8* bitcast (%KlassInfo.0*
 *          @"_CNat16OutOfMemoryErrorE.objKlass" to i8*))
 *   br i1 %3, label %is.OOM, label %judge.Error
 *
 * is.OOM:                                      ; preds = %unwindDest
 *   invoke void @_CNat8eprintlnHRNat6StringE(...)
 *        to label %normalDest2 unwind label %rethrow
 *
 * normalDest2:                                 ; preds = %is.OOM
 *   br label %judge.end
 *
 * judge.Error:                                 ; preds = %unwindDest
 *   %x = call i1 @llvm.cj.is.instance.of(i8 addrspace(1)* %8, i8* bitcast (%KlassInfo.1*
 *           @_CNat5ErrorE.objKlass to i8*))
 *   br i1 %x, label %is.Error, label %judge.Exception
 *
 * is.Error:                                    ; preds = %judge.Error
 *   %4 = call i8* @llvm.cj.get.virtual.func(i8 addrspace(1)* noalias %2, i64 3)
 *   %5 = bitcast i8* %4 to void (%Unit.Type*, i8 addrspace(1)*)*
 *   invoke void %5(%Unit.Type* noalias sret(%Unit.Type) %X, i8 addrspace(1)* %2)
 *        to label %normalDest3 unwind label %rethrow
 *
 * normalDest3:                                 ; preds = %is.Error
 *   br label %judge.end
 *
 * judge.Exception:                             ; preds = %judge.Error
 *   %6 = call i1 @llvm.cj.is.instance.of(i8 addrspace(1)* %2, i8* bitcast (%KlassInfo.0*
 *          @"_CNat9ExceptionE.objKlass" to i8*))
 *   br i1 %6, label %is.Exception, label %judge.end
 *
 * is.Exception:                                ; preds = %judge.Exception
 *   invoke void @"_CNat15handleExceptionHCNat9ExceptionE"(%Unit.Type* noalias sret(%Unit.Type) %X, i8
 *          addrspace(1)* %2)
 *        to label %normalDest4 unwind label %rethrow
 *
 * normalDest4:                                 ; preds = %is.Exception
 *   br label %judge.end
 *
 * judge.end:                                   ; preds = %is.Exception, %judge.Exception, %is.Error, %is.OOM
 *   call void @llvm.cj.end.catch()
 *   call void @"_CNat27CJ_CORE_ExecAtexitCallbacksEv"(%Unit.Type* %X)
 *   ret xxx
 *
 * rethrow:                                     ; preds = %judge.end, %is.Exception, %is.Error
 *   %17 = landingpad token
 *        catch i8* null
 *   call void @llvm.cj.end.catch()
 *   call void @"_CNat27CJ_CORE_ExecAtexitCallbacksEv"(%Unit.Type* noalias sret(%Unit.Type) %0)
 *   ret xxx
 */
void CreateUnwindBlockForTryCatchWrapper(
    IRBuilder2& irBuilder, const std::function<void()>& createRetInst, bool needAtexitCallbacks)
{
    auto& cgMod = irBuilder.GetCGModule();
    auto classOutOfMemoryErrorDef = StaticCast<CHIR::ClassDef*>(
        GetTypeDefFromImplicitUsedFuncParam(cgMod, "_CNat16OutOfMemoryError6<init>Hv", 0));
    auto classErrorDef = StaticCast<CHIR::ClassDef*>(
        GetTypeDefFromImplicitUsedFuncParam(cgMod, "_CNat5Error15printStackTraceHv", 0));
    auto classExceptionDef = StaticCast<CHIR::ClassDef*>(
        GetTypeDefFromImplicitUsedFuncParam(cgMod, "_CNat9Exception15printStackTraceHv", 0));
    auto& cgCtx = irBuilder.GetCGContext();
    // Generate IR for landPadBb BasicBlock
    auto landingPad = irBuilder.CreateLandingPad(CGType::GetLandingPadType(cgCtx.GetLLVMContext()), 0);
    landingPad->addClause(llvm::Constant::getNullValue(irBuilder.getInt8PtrTy()));
    auto exceptionObjWrapper = irBuilder.CallExceptionIntrinsicGetExceptionValue();
    auto exceptionValue = irBuilder.CallPostThrowExceptionIntrinsic(exceptionObjWrapper);
    // Create basicBlocks for catching Exception and Error, These BBs need to be inserted under the LandingPad.
    auto [isOOMBb, judgeErrorBb, isErrorBb, judgeExceptionBb, isExceptionBb, judgeEndBb, rethowBb] =
        Vec2Tuple<7>(irBuilder.CreateAndInsertBasicBlocks(
            {"is.OOM", "judge.Error", "is.Error", "judge.Exception", "is.Exception", "judge.end", "rethrow"}));
    // 1. attempt to capture Error or Exception
    {
        CodeGenUnwindBlockScope unwindBlockScope(cgMod, rethowBb);
        // 1.1. attempt to capture OutOfMemoryError
        auto isOOM = irBuilder.CallClassIntrinsicInstanceOf(exceptionValue, classOutOfMemoryErrorDef->GetType());
        (void)irBuilder.CreateCondBr(isOOM, isOOMBb, judgeErrorBb);
        // 1.2. successfully captured an Error
        irBuilder.SetInsertPoint(isOOMBb);
        irBuilder.CreateEPrintlnCall("An exception has occurred:");
        irBuilder.CreateEPrintlnCall("    Out of memory");
        (void)irBuilder.CreateBr(judgeEndBb);
        // 1.3. attempt to capture an Error
        irBuilder.SetInsertPoint(judgeErrorBb);
        auto isError = irBuilder.CallClassIntrinsicInstanceOf(exceptionValue, classErrorDef->GetType());
        (void)irBuilder.CreateCondBr(isError, isErrorBb, judgeExceptionBb);
        // 1.4. successfully captured an Error
        irBuilder.SetInsertPoint(isErrorBb);
        CreatePrintStackTraceCall(irBuilder, exceptionValue);
        (void)irBuilder.CreateBr(judgeEndBb);
        // 1.5. attempt to capture an Exception
        irBuilder.SetInsertPoint(judgeExceptionBb);
        auto isException = irBuilder.CallClassIntrinsicInstanceOf(exceptionValue, classExceptionDef->GetType());
        (void)irBuilder.CreateCondBr(isException, isExceptionBb, judgeEndBb);
        // 1.6. successfully captured an Exception
        irBuilder.SetInsertPoint(isExceptionBb);
        irBuilder.CreateHandleExceptionCall(
            {irBuilder.CreateEntryAlloca(CGType::GetUnitType(cgCtx.GetLLVMContext())), exceptionValue});
        (void)irBuilder.CreateBr(judgeEndBb);
    }
    // 2. Capture completed
    irBuilder.SetInsertPoint(judgeEndBb);
    if (needAtexitCallbacks) {
        irBuilder.CreateExecAtExitCallbacksCall();
    }
    createRetInst();
    // 3. rethrow
    irBuilder.SetInsertPoint(rethowBb);
    auto landingPad1 = irBuilder.CreateLandingPad(CGType::GetLandingPadType(cgCtx.GetLLVMContext()), 0);
    landingPad1->addClause(llvm::Constant::getNullValue(irBuilder.getInt8PtrTy()));
    if (needAtexitCallbacks) {
        irBuilder.CreateExecAtExitCallbacksCall();
    }
    createRetInst();
}

/* @brief Create a wrapper of try-catch:
 * try {
 *   createTryScopeInst() ; try scope instruction
 * } catch (e: Error) {
 *   e.printStackTrace()
 *   createRetInst()      ; the return instructions while an exception occurs
 * } catch (e: Exception) {
 *   handleException(e)
 *   createRetInst()      ; the return instructions while an exception occurs
 * }
 */
void CreateTryCatchWrapper(IRBuilder2& irBuilder, const std::function<void()>& createTryScopeInst,
    const std::function<void()>& createRetInst, bool needAtexitCallbacks)
{
    auto unwindBlock = irBuilder.CreateAndInsertBasicBlocks({"unwindDest"})[0];
    {
        CodeGenUnwindBlockScope unwindBlockScope(irBuilder.GetCGModule(), unwindBlock);
        createTryScopeInst();
    }
    irBuilder.SetInsertPoint(unwindBlock);
    CreateUnwindBlockForTryCatchWrapper(irBuilder, createRetInst, needAtexitCallbacks);
}

llvm::Function* GenerateEntryFunction(CGModule& cgMod, llvm::Function& userMain)
{
    IRBuilder2 irBuilder(cgMod);
    auto cjEntryFuncType = llvm::FunctionType::get(irBuilder.getInt32Ty(), {}, false);
    auto cjEntryFunc = llvm::cast<llvm::Function>(
        cgMod.GetLLVMModule()->getOrInsertFunction(CJ_ENTRY_FUNC_NAME, cjEntryFuncType).getCallee());
    cjEntryFunc->setPersonalityFn(cgMod.GetExceptionIntrinsicPersonality());
    SetGCCangjie(cjEntryFunc);

    auto entryBB = llvm::BasicBlock::Create(cgMod.GetLLVMContext(), "entry", cjEntryFunc);
    irBuilder.SetInsertPoint(entryBB);

    (void)irBuilder.CallIntrinsicFunction(
        irBuilder.getVoidTy(), PREFIX_OF_BACKEND_SYMS + "CheckThreadLocalDataOffset", {});

    auto createTryScopeInst = [&irBuilder, &userMain]() {
        auto& cgMod = irBuilder.GetCGModule();
        auto globalInitFunc = cgMod.GetOrInsertCGFunction(cgMod.GetCGContext().GetCHIRPackage().GetPackageInitFunc());
        CJC_ASSERT(globalInitFunc && "Global init function should exist.");
        (void)irBuilder.CreateCallOrInvoke(globalInitFunc->GetRawFunction(), {});

        // Create user.main function call
        std::vector<llvm::Value*> userMainArgs{};
        if (!userMain.arg_empty()) {
            auto getCommandLineArgsFuncCHIRNode =
                cgMod.GetCGContext().GetImplicitUsedFunc("_CNat18getCommandLineArgsHv");
            auto getCommandLineArgsFuncReturnType =
                StaticCast<CHIR::FuncType*>(getCommandLineArgsFuncCHIRNode->GetType())->GetReturnType();
            auto retCGType = CGType::GetOrCreate(cgMod, getCommandLineArgsFuncReturnType);
            auto commandLineArgs = irBuilder.CreateEntryAlloca(retCGType->GetLLVMType());
            irBuilder.CreateCJMemSetStructWith0(commandLineArgs);
            irBuilder.CreateGetCommandLineArgsCall({commandLineArgs});
            userMainArgs.emplace_back(irBuilder.CreatePointerBitCastOrAddrSpaceCast(
                commandLineArgs, userMain.args().begin()->getType()));
        }
        auto userMainRetVal = irBuilder.CreateCallOrInvoke(&userMain, userMainArgs);
        irBuilder.CreateExecAtExitCallbacksCall();
        (void)irBuilder.CreateRet(GenerateMainRetVal(irBuilder, userMainRetVal));
    };
    auto createRetInst = [&irBuilder]() { irBuilder.CreateRet(llvm::ConstantInt::get(irBuilder.getInt32Ty(), 1)); };
    CreateTryCatchWrapper(irBuilder, createTryScopeInst, createRetInst, true);
    return cjEntryFunc;
}
} // namespace

llvm::Function* CreateMainFunc(const CGModule& cgMod);

void EmitMain(CGModule& cgMod)
{
    if (!cgMod.GetCGContext().GetCompileOptions().CompileExecutable()) {
        return;
    }

    Utils::ProfileRecorder recorder("EmitIR", "EmitMain");
    auto chirUserMain = cgMod.GetCGContext().GetCGPkgContext().FindCHIRGlobalValue(USER_MAIN_MANGLED_NAME);
    CJC_ASSERT(chirUserMain && "Cannt find userMain.");
    auto userMainFunc = cgMod.GetOrInsertCGFunction(chirUserMain);

    auto mainFunction = CreateMainFunc(cgMod);
    auto entryBB = llvm::BasicBlock::Create(cgMod.GetLLVMContext(), "entry", mainFunction);

    IRBuilder2 irBuilder(cgMod, entryBB);
    auto& llvmCtx = cgMod.GetLLVMContext();
    auto voidType = llvm::Type::getVoidTy(llvmCtx);
    /// @main func call CjRuntimeInit
    auto fType = llvm::FunctionType::get(voidType, false);
    auto f = llvm::cast<llvm::Function>(
        cgMod.GetLLVMModule()->getOrInsertFunction(PREFIX_OF_RUNTIME_SYMS + "CjRuntimeInit", fType).getCallee());
    (void)irBuilder.CreateCallOrInvoke(fType, f, {});

    auto argcValue = mainFunction->args().begin();
    auto argvValue = mainFunction->args().begin() + 1;
    /// @main func call SetCommandLineArgs
    fType = llvm::FunctionType::get(voidType, {argcValue->getType(), argvValue->getType()}, false);
    f = llvm::cast<llvm::Function>(
        cgMod.GetLLVMModule()->getOrInsertFunction(PREFIX_OF_RUNTIME_SYMS + "SetCommandLineArgs", fType).getCallee());
    (void)irBuilder.CreateCallOrInvoke(fType, f, {argcValue, argvValue});

    // Create @cj_entry func
    auto cjEntryFunc = GenerateEntryFunction(cgMod, *userMainFunc->GetRawFunction());
    CJC_ASSERT(cjEntryFunc != nullptr);

    /// @main func call CjRuntimeStart, and it will execute @user.main.
    fType = llvm::FunctionType::get(voidType, {cjEntryFunc->getType()}, false);
    f = llvm::cast<llvm::Function>(
        cgMod.GetLLVMModule()->getOrInsertFunction(PREFIX_OF_RUNTIME_SYMS + "CjRuntimeStart", fType).getCallee());
    (void)irBuilder.CreateCallOrInvoke(fType, f, {cjEntryFunc});

    (void)irBuilder.CreateRetVoid();
}

llvm::Function* GetGVResetCallBack(CGModule& cgMod, llvm::FunctionType* callBackFuncType)
{
    auto& llvmCtx = cgMod.GetLLVMContext();
    auto wrapFuncName = "wrapper.F0uPuE";
    auto voidType = llvm::Type::getVoidTy(llvmCtx);
    auto wrapFuncType = llvm::FunctionType::get(
        voidType, {callBackFuncType->getPointerTo(), llvm::Type::getInt8Ty(llvmCtx)->getPointerTo()}, false);
    auto wrapFunc =
        llvm::cast<llvm::Function>(cgMod.GetLLVMModule()->getOrInsertFunction(wrapFuncName, wrapFuncType).getCallee());
    auto entryBB = llvm::BasicBlock::Create(llvmCtx, "entry", wrapFunc);
    IRBuilder2 irBuilder(cgMod, entryBB);
    irBuilder.LLVMIRBuilder2::CreateCall(callBackFuncType, wrapFunc->getArg(0), {wrapFunc->getArg(1)});
    (void)irBuilder.CreateRetVoid();
    wrapFunc->setLinkage(llvm::GlobalValue::PrivateLinkage);
    AddFnAttr(wrapFunc, llvm::Attribute::NoInline);
    AddFnAttr(wrapFunc, llvm::Attribute::get(llvmCtx, CJ2C_ATTR));
    return wrapFunc;
}

void CollectDependentPackages(llvm::Function& func, std::vector<std::string>& giList)
{
    const std::string CALL_DEPENDENT_PACKAGE_INIT_SUFFIX =
        SPECIAL_NAME_FOR_INIT_FLAG_RESET_FUNCTION + MANGLE_FUNC_PARAM_TYPE_PREFIX + MANGLE_VOID_TY_SUFFIX;
    const std::string CALL_DEPENDENT_PACKAGES_INITS_SUFFIX =
        SPECIAL_NAME_FOR_IMPORTS_INIT_FUNCTION + MANGLE_FUNC_PARAM_TYPE_PREFIX + MANGLE_VOID_TY_SUFFIX;
    for (auto& block : func.getBasicBlockList()) {
        for (auto& inst : block) {
            auto ci = llvm::dyn_cast<llvm::CallInst>(&inst);
            if (!ci) {
                continue;
            }
            auto callee = ci->getCalledFunction();
            if (!callee) {
                continue;
            }
            auto calleeName = callee->getName();
            auto calleeNamePrefixSize = calleeName.str().size() - CALL_DEPENDENT_PACKAGE_INIT_SUFFIX.size();
            auto calleePrefix = calleeName.str().substr(0, calleeNamePrefixSize);
            auto calleeSuffix = calleeName.str().substr(calleeNamePrefixSize);
            if (calleeSuffix == CALL_DEPENDENT_PACKAGES_INITS_SUFFIX) {
                CollectDependentPackages(*callee, giList);
            } else if (calleeName.startswith(MANGLE_CANGJIE_PREFIX + MANGLE_GLOBAL_PACKAGE_INIT_PREFIX)) {
                giList.emplace_back(calleePrefix + CALL_DEPENDENT_PACKAGE_INIT_SUFFIX);
            }
        }
    }
}

void CallDependentPackageGlobalResetCall(IRBuilder2 & irBuilder)
{
    auto& cgCtx = irBuilder.GetCGContext();
    auto llvmMod = irBuilder.GetLLVMModule();
    auto llvmFunc = llvmMod->getFunction(cgCtx.GetCHIRPackage().GetPackageInitFunc()->GetIdentifierWithoutPrefix());
    CJC_ASSERT(llvmFunc);
    std::vector<std::string> giList;
    CollectDependentPackages(*llvmFunc, giList);
    auto giFuncType = llvm::FunctionType::get(irBuilder.getVoidTy(), {}, false);
    for (auto gi : giList) {
        auto flagResetFunc = llvm::cast<llvm::Function>(llvmMod->getOrInsertFunction(gi, giFuncType).getCallee());
        flagResetFunc->addFnAttr(llvm::Attribute::NoInline);
        irBuilder.LLVMIRBuilder2::CreateCall(giFuncType, flagResetFunc);
    }
}

llvm::Function* CreatePackageInitFlagResetFunction(CGModule& cgMod)
{
    auto& cgCtx = cgMod.GetCGContext();
    auto llvmMod = cgMod.GetLLVMModule();
    auto pkgInitFuncName = cgCtx.GetCHIRPackage().GetPackageInitFunc()->GetIdentifierWithoutPrefix();
    std::string targetSuffix = SPECIAL_NAME_FOR_INIT_FLAG_RESET_FUNCTION + MANGLE_FUNC_PARAM_TYPE_PREFIX +
        MANGLE_VOID_TY_SUFFIX;
    auto funcName = pkgInitFuncName.substr(0, pkgInitFuncName.size() - targetSuffix.size()) + targetSuffix;
    if (auto f = llvmMod->getFunction(funcName)) {
        return f;
    }

    auto voidType = llvm::Type::getVoidTy(llvmMod->getContext());
    auto functionType = llvm::FunctionType::get(voidType, {}, false);
    auto func = cgMod.GetOrInsertFunction(funcName, functionType);
    AddFnAttr(func, llvm::Attribute::NoInline);
    func->setPersonalityFn(cgMod.GetExceptionIntrinsicPersonality());
    AddLinkageTypeMetadata(*func, llvm::GlobalValue::ExternalLinkage, cgCtx.IsCGParallelEnabled());
    SetGCCangjie(func);

    IRBuilder2 irBuilder(cgMod);
    auto entryBB = irBuilder.CreateEntryBasicBlock(func, "entry");
    irBuilder.SetInsertPoint(entryBB);

    // step 1: call flag reset functions of dependent packages.
    CallDependentPackageGlobalResetCall(irBuilder);

    // Step 2: store i1 false, i1* @"has_invoke_xx_global_init$_primitive.
    if (auto resetFlag = cgMod.GetLLVMModule()->getGlobalVariable("has_invoked_pkg_init_literal", true)) {
        (void)irBuilder.CreateStore(irBuilder.getFalse(), resetFlag);
    }

    // Step 3: store i1 false, i1* @"has_invoke_xx_global_init$.
    if (auto initFlag = cgMod.GetLLVMModule()->getGlobalVariable(CHIR::GV_PKG_INIT_ONCE_FLAG, true)) {
        (void)irBuilder.CreateStore(irBuilder.getFalse(), initFlag);
    }

    (void)irBuilder.CreateRetVoid();
    return func;
}

void RegisterExceptionRaiser(CGModule& cgMod)
{
    if (cgMod.GetCGContext().GetCurrentPkgName() == CORE_PACKAGE_NAME) {
        auto& llvmCtx = cgMod.GetLLVMContext();
        auto module = cgMod.GetLLVMModule();
        auto pkgInitFunc = module->getFunction(
            cgMod.GetCGContext().GetCHIRPackage().GetPackageInitFunc()->GetIdentifierWithoutPrefix());
        auto bi = llvm::cast<llvm::BranchInst>(pkgInitFunc->getEntryBlock().getTerminator());
        CJC_ASSERT(bi != nullptr);
        auto bb = bi->getSuccessor(1);
        CJC_ASSERT(bb != nullptr);
        IRBuilder2 irBuilder(cgMod);
        irBuilder.SetInsertPoint(bb->getTerminator());
        auto int8PtrType = llvm::Type::getInt8PtrTy(llvmCtx);
        auto chirFunc = cgMod.GetCGContext().GetCGPkgContext().FindCHIRGlobalValue("rt$ThrowImplicitException");
        auto func = cgMod.GetOrInsertCGFunction(chirFunc)->GetRawFunction();
        auto param = irBuilder.CreateBitCast(func, int8PtrType);
        // declare void @cj_register_implicit_exception_raisers(i8*)
        llvm::Function* registerExceptionFunc =
            llvm::Intrinsic::getDeclaration(module, llvm::Intrinsic::cj_register_implicit_exception_raisers);
        (void)irBuilder.LLVMIRBuilder2::CreateCall(registerExceptionFunc, {param});
    }
}

void CreatePackageInitResetFunction(CGModule& cgMod)
{
    auto llvmMod = cgMod.GetLLVMModule();
    std::string pkgInitFuncName = cgMod.GetCGContext().GetCHIRPackage().GetPackageInitFunc()->
        GetIdentifierWithoutPrefix();
    std::string targetSuffix = SPECIAL_NAME_FOR_INIT_RESET_FUNCTION + MANGLE_FUNC_PARAM_TYPE_PREFIX +
        MANGLE_VOID_TY_SUFFIX;
    std::string funcName = pkgInitFuncName.substr(0, pkgInitFuncName.size() - targetSuffix.size()) + targetSuffix;
    if (!llvmMod->getFunction(funcName)) {
        /**
         * define void @"xx_global_init$_reset"(i8* %param).
         * struct param {
         *      cFuncType* cFuncPtr;
         *      i8* cFuncParam;
         * }
         */
        IRBuilder2 irBuilder(cgMod);
        auto functionType = llvm::FunctionType::get(irBuilder.getVoidTy(), {irBuilder.getInt8PtrTy()}, false);
        auto func = cgMod.GetOrInsertFunction(funcName, functionType);
        func->arg_begin()->setName("param");
        AddFnAttr(func, llvm::Attribute::NoInline);
        func->setPersonalityFn(cgMod.GetExceptionIntrinsicPersonality());
        AddLinkageTypeMetadata(*func, llvm::GlobalValue::ExternalLinkage, cgMod.GetCGContext().IsCGParallelEnabled());
        SetGCCangjie(func);
        auto entryBB = irBuilder.CreateEntryBasicBlock(func, "entry");
        CodeGenFunctionScope funcScope(irBuilder, func);
        irBuilder.SetInsertPoint(entryBB);
        auto createTryScopeInst = [&irBuilder, func, &pkgInitFuncName]() {
            auto& cgMod = irBuilder.GetCGModule();
            auto llvmMod = irBuilder.GetLLVMModule();
            // Step 1: reset all package init flag to `false`
            auto flagResetFunc = CreatePackageInitFlagResetFunction(cgMod);
            (void)irBuilder.CreateCallOrInvoke(flagResetFunc, {});

            // Step 2: re-initialize the literal GVs.
            std::string targetSuffix = SPECIAL_NAME_FOR_INIT_LITERAL_FUNCTION + MANGLE_FUNC_PARAM_TYPE_PREFIX +
                MANGLE_VOID_TY_SUFFIX;
            auto literalInitFunc = llvmMod->getFunction(
                pkgInitFuncName.substr(0, pkgInitFuncName.size() - targetSuffix.size()) + targetSuffix);
            if (literalInitFunc) {
                (void)irBuilder.CreateCallOrInvoke(literalInitFunc, {});
            }

            // Step 3: re-initialize the non-literal GVs.
            auto gvInitFunc = llvmMod->getFunction(pkgInitFuncName);
            CJC_NULLPTR_CHECK(gvInitFunc);
            (void)irBuilder.CreateCallOrInvoke(gvInitFunc, {});

            auto cFuncType = llvm::FunctionType::get(irBuilder.getVoidTy(), {irBuilder.getInt8PtrTy()}, false);
            auto param = llvm::StructType::getTypeByName(llvmMod->getContext(), "struct._param");
            if (!param) {
                param = llvm::StructType::create(llvmMod->getContext(), "struct._param");
            }
            SetStructTypeBody(param, std::vector<llvm::Type*>{cFuncType->getPointerTo(), irBuilder.getInt8PtrTy()});
            /// Add a wrapper function for the CFunc (for details see GetIndirectCFuncCallWrapper).
            auto wrapperFunc = GetGVResetCallBack(cgMod, cFuncType);
            auto castParam = irBuilder.CreateBitCast(func->arg_begin(), param->getPointerTo());
            (void)irBuilder.CreateCallOrInvoke(wrapperFunc, {
                // 0: the index of cfunc
                irBuilder.LLVMIRBuilder2::CreateLoad(
                    param->getStructElementType(0), irBuilder.CreateStructGEP(param, castParam, 0)),
                // 1: the index of cFunc param
                irBuilder.LLVMIRBuilder2::CreateLoad(
                    param->getStructElementType(1), irBuilder.CreateStructGEP(param, castParam, 1))
            });
            (void)irBuilder.CreateRetVoid();
        };
        createTryScopeInst();
    }
}

void CreateLLVMUsedGVs(const CGModule& cgMod)
{
    const auto& llvmUsedGVs = cgMod.GetCGContext().GetLLVMUsedVars();
    if (llvmUsedGVs.empty()) {
        return;
    }

    auto i8pTy = llvm::Type::getInt8PtrTy(cgMod.GetLLVMContext());
    std::vector<llvm::Constant*> gvOrGFs{};
    gvOrGFs.reserve(llvmUsedGVs.size());
    for (const auto& gvName : llvmUsedGVs) {
        if (auto gv = cgMod.GetLLVMModule()->getNamedValue(gvName)) {
            (void)gvOrGFs.emplace_back(llvm::ConstantExpr::getBitCast(gv, i8pTy));
        }
    }
    auto arrType = llvm::ArrayType::get(i8pTy, gvOrGFs.size());
    auto llvmUsedGV = llvm::cast<llvm::GlobalVariable>(cgMod.GetLLVMModule()->getOrInsertGlobal("llvm.used", arrType));
    llvmUsedGV->setConstant(false);
    llvmUsedGV->setInitializer(llvm::ConstantArray::get(arrType, gvOrGFs));
    llvmUsedGV->setSection("llvm.metadata");
    llvmUsedGV->setLinkage(llvm::GlobalValue::AppendingLinkage);
}

void ReplaceFunction(CGModule& cgMod)
{
    if (!cgMod.GetCGContext().GetCompileOptions().enableCompileDebug) {
        return;
    }

    /// Briefly, we want to rewrite the CallInst from LHS to RHS.
    // call void @mutF$withoutTI(%thisWithoutTI, %basePtr, %arg1) --> call void @mutF(%thisWithTI, %arg1)
    // call void @nonMutF$withoutTI(%thisWithoutTI, %arg1)        --> call void @nonMutF(%thisWithTI, %arg1)
    IRBuilder2 irBuilder(cgMod);
    auto& callBasesToReplace = cgMod.GetCGContext().GetCallBasesToReplace();
    for (auto& item : callBasesToReplace) {
        auto& applyW = item.applyExprW;
        irBuilder.SetInsertCGFunction(*cgMod.GetOrInsertCGFunction(applyW.GetTopLevelFunc()));
        auto oldCall = item.callWithoutTI;
        irBuilder.SetInsertPoint(oldCall);
        /// step1: prepare new arguments
        bool hasSRet = oldCall->hasStructRetAttr();
        auto thisParamOffset = hasSRet ? 1U : 0U;
        llvm::Value* thisParamWithoutTI = *(oldCall->arg_begin() + thisParamOffset);
        std::vector<llvm::Value*> argsVal{};
        for (auto& arg : oldCall->args()) {
            argsVal.emplace_back(&(*arg));
        }
        bool isCalleeMutOrCtor = applyW.IsCalleeStructMutOrCtorMethod();
        // drop the `basePtr` parameter for mut function
        llvm::Value* basePtr = nullptr;
        if (isCalleeMutOrCtor) {
            auto basePtrItor = argsVal.begin() + thisParamOffset + 1U;
            basePtr = *basePtrItor;
            argsVal.erase(basePtrItor);
        }
        /// step2: alloca memory for `this` with TypeInfo
        CJC_NULLPTR_CHECK(applyW.GetThisParam());
        auto thisCHIRType = DeRef(*applyW.GetThisParam()->GetType());
        cgMod.GetCGContext().genericParamsCacheMap[irBuilder.GetInsertFunction()].clear();
        cgMod.GetCGContext().genericParamsSizeBlockLevelCacheMap[irBuilder.GetInsertBlock()].clear();
        auto thisParamTypeInfo = irBuilder.CreateTypeInfo(thisCHIRType);
        auto size32 = irBuilder.GetLayoutSize_32(*thisCHIRType);
        auto size64 = irBuilder.CreateSExt(size32, irBuilder.getInt64Ty());
        auto thisParamWithTI = irBuilder.CallIntrinsicAllocaGeneric({thisParamTypeInfo, size32});
        argsVal[thisParamOffset] = thisParamWithTI;
        /// step3: store `this` without TypeInfo to the memory allocated by step2
        auto payloadPtr = irBuilder.GetPayloadFromObject(thisParamWithTI);
        if (auto thisType = CGType::GetOrCreate(cgMod, thisCHIRType)->GetLLVMType(); IsTypeContainsRef(thisType)) {
            if (isCalleeMutOrCtor) {
                auto load = irBuilder.CreateEntryAlloca(thisType);
                (void)irBuilder.CreateCJMemSetStructWith0(load);
                irBuilder.CallGCReadAgg({load, basePtr, thisParamWithoutTI, size64});
                irBuilder.CallGCWriteAgg({thisParamWithTI, payloadPtr, load, size64});
            } else {
                irBuilder.CallGCWriteAgg({thisParamWithTI, payloadPtr, thisParamWithoutTI, size64});
            }
        } else {
            irBuilder.CreateMemCpy(payloadPtr, llvm::MaybeAlign(), thisParamWithoutTI, llvm::MaybeAlign(), size32);
        }
        /// step4: emit a new CallInst with "xxx"
        auto callee = cgMod.GetOrInsertCGFunction(applyW.GetCallee())->GetWrapperFunction();
        CJC_NULLPTR_CHECK(callee);
        llvm::CallBase* newCall = nullptr;
        if (llvm::isa<llvm::CallInst>(oldCall)) {
            newCall = irBuilder.LLVMIRBuilder2::CreateCall(callee, argsVal);
            irBuilder.SetInsertPoint(oldCall->getNextNode());
        } else if (auto invokeInst = llvm::dyn_cast<llvm::InvokeInst>(oldCall)) {
            auto normalDest = invokeInst->getNormalDest();
            auto unwindDest = invokeInst->getUnwindDest();
            newCall = irBuilder.LLVMIRBuilder2::CreateInvoke(callee, normalDest, unwindDest, argsVal);
            irBuilder.SetInsertPoint(normalDest, normalDest->getFirstInsertionPt());
        }
        if (hasSRet) {
            auto sretAttr =
                oldCall->getAttributeAtIndex(llvm::AttributeList::FirstArgIndex, llvm::Attribute::StructRet);
            newCall->addAttributeAtIndex(llvm::AttributeList::FirstArgIndex, sretAttr);
            newCall->addAttributeAtIndex(llvm::AttributeList::FirstArgIndex, llvm::Attribute::NoAlias);
        }
        oldCall->replaceAllUsesWith(newCall);
        oldCall->eraseFromParent();
        /// step5: find out the BB to update `this` without TypeInfo
        // Note: non-mut function could skip this step. mut or ctor function should do this step.
        if (!isCalleeMutOrCtor) {
            continue;
        }
        if (auto thisType = CGType::GetOrCreate(cgMod, thisCHIRType)->GetLLVMType(); IsTypeContainsRef(thisType)) {
            auto load = irBuilder.CreateEntryAlloca(thisType);
            (void)irBuilder.CreateCJMemSetStructWith0(load);
            irBuilder.CallGCReadAgg({load, thisParamWithTI, payloadPtr, size64});
            irBuilder.CallGCWriteAgg({basePtr, thisParamWithoutTI, load, size64});
        } else {
            irBuilder.CreateMemCpy(thisParamWithoutTI, llvm::MaybeAlign(), payloadPtr, llvm::MaybeAlign(), size32);
        }
    }
}

void InlineFunction(CGModule& cgMod)
{
    if (!cgMod.GetCGContext().GetCompileOptions().enableCompileDebug) {
        return;
    }

    // Briefly, we want to inline the @mutF$withoutTI(%thisWithoutTI, %basePtr, %arg1)
    // to the @mutF(%thisWithTI, %arg1).
    auto findAllocInstOfThisWithoutTI = [](llvm::Function* function) -> llvm::Instruction* {
        llvm::Instruction* allocInstOfThisWithoutTI = nullptr;
        auto& entryBB = function->getEntryBlock();
        for (auto& inst : entryBB.getInstList()) {
            if (inst.getOpcode() == llvm::Instruction::Alloca && inst.getName().equals("this.debug.i")) {
                allocInstOfThisWithoutTI = &inst;
            }
        }
        CJC_ASSERT(allocInstOfThisWithoutTI && "Alloc inst not found.");
        return allocInstOfThisWithoutTI;
    };

    IRBuilder2 irBuilder(cgMod);
    llvm::InlineFunctionInfo fnInfo;
    auto& callBasesToInline = cgMod.GetCGContext().GetCallBasesToInline();
    for (auto item : callBasesToInline) {
        auto callBase = item.first;
        auto retInst = item.second;
        // step1: get information of callee
        auto callee = callBase->getCalledFunction();
        CJC_NULLPTR_CHECK(callee);
        auto sp = callee->getSubprogram();
        // step2: inline the call
        auto parentFunction = callBase->getFunction();
        auto inlineRes = llvm::InlineFunction(*callBase, fnInfo, nullptr, false);
        if (!inlineRes.isSuccess()) {
            Errorln(inlineRes.getFailureReason());
            CJC_ASSERT(false && "Can't be inlined.");
        }
        auto funcNameMD = llvm::MDString::get(cgMod.GetLLVMContext(), parentFunction->getName());
        sp->replaceRawLinkageName(funcNameMD);
        parentFunction->setSubprogram(sp);
        auto debugLocOfRetExpr = cgMod.GetCGContext().GetDebugLocOfRetExpr(callee);
        if (debugLocOfRetExpr.size() == 1) {
            auto beginPos = debugLocOfRetExpr.begin()->GetBeginPos();
            retInst->setDebugLoc(cgMod.diBuilder->CreateDILoc(sp, beginPos));
        }
        callee->setSubprogram(nullptr);
        // step3: update the dbgDeclare of 'this'
        llvm::Value* thisWithTI = nullptr;
        for (auto& arg : parentFunction->args()) {
            if (arg.getName().equals("this.withTI")) {
                thisWithTI = &arg;
                break;
            }
        }
        irBuilder.SetInsertPoint(parentFunction->getEntryBlock().getTerminator());
        CJC_NULLPTR_CHECK(thisWithTI);
        auto debugThis = irBuilder.CreateEntryAlloca(thisWithTI->getType(), nullptr, thisWithTI->getName() + ".debug");
        (void)irBuilder.CreateStore(thisWithTI, debugThis);
        auto thisWithoutTI = findAllocInstOfThisWithoutTI(parentFunction);
        auto thisParamMetadata = llvm::ValueAsMetadata::getIfExists(thisWithoutTI);
        CJC_NULLPTR_CHECK(thisParamMetadata);
        llvm::cast<llvm::ReplaceableMetadataImpl>(thisParamMetadata)
            ->replaceAllUsesWith(llvm::ValueAsMetadata::get(debugThis));
    }
}

namespace {
llvm::Constant* GetReadOnlyArrayKlassInfo(const CGModule& cgMod)
{
    auto module = cgMod.GetLLVMModule();
    static const std::string name("RawArray<UInt8>.ti");
    if (auto gv = module->getGlobalVariable(name, true); gv) {
        return gv;
    }
    auto& ctx = cgMod.GetLLVMContext();
    auto& cgCtx = cgMod.GetCGContext();

    // Generate Type ArrayLayout.UInt8
    auto classInfoType = CGType::GetOrCreateTypeInfoType(ctx);
    auto gv = llvm::cast<llvm::GlobalVariable>(module->getOrInsertGlobal(name, classInfoType));
    CJC_NULLPTR_CHECK(gv);
    std::vector<llvm::Constant*> klassConstants = cgMod.InitRawArrayUInt8Constants();
    gv->setInitializer(llvm::ConstantStruct::get(llvm::cast<llvm::StructType>(classInfoType), klassConstants));
    gv->addAttribute(GC_KLASS_ATTR);
    AddLinkageTypeMetadata(*gv, llvm::GlobalValue::InternalLinkage, false);

    // Generate ArrayLayout.UInt8 here to ensure it is created.
    auto layoutType =
        CGArrayType::GenerateArrayLayoutTypeInfo(cgCtx, ARRAY_LAYOUT_PREFIX + "UInt8", llvm::Type::getInt8Ty(ctx));
    auto meta = llvm::MDTuple::get(ctx, {llvm::MDString::get(ctx, layoutType->getStructName())});
    gv->setMetadata(GC_TYPE_META_NAME, meta);
    return gv;
}
} // namespace

void InitializeCjStringLiteral(const CGModule& cgMod)
{
    auto& ctx = cgMod.GetLLVMContext();
    auto int8PtrType = llvm::Type::getInt8PtrTy(ctx);
    auto int32Type = llvm::Type::getInt32Ty(ctx);
    auto int64Type = llvm::Type::getInt64Ty(ctx);

    auto& cjStrings = cgMod.GetCGContext().GetCJStrings();
    if (cjStrings.empty()) {
        return;
    }

    // 1. Traverse all cj string literals' data, concatenate them as a big string named rawData
    std::set<std::string> cjStringContents{};
    // 1.1 Sort and deduplicate cjStringContents to obtain the minimum rawData
    for (auto iter = cjStrings.begin(); iter != cjStrings.end(); ++iter) {
        auto& cjStringName = iter->first;
        auto& cjStringContent = iter->second;
        if (cgMod.GetLLVMModule()->getNamedValue(cjStringName)) {
            cjStringContents.emplace(cjStringContent);
        } else {
            // cjString may be codeGen built-in data and optimized.
        }
    }
    // 1.1 Smaller rawData can be obtained by reverse order
    std::string rawData = "";
    for (auto iter = cjStringContents.crbegin(); iter != cjStringContents.crend(); ++iter) {
        auto& cjStringContent = *iter;
        if (rawData.find(cjStringContent) == std::string::npos) {
            rawData.append(cjStringContent);
        }
    }

    // 2. Construct RawArray which stores all cj string literal data
    auto strContent = llvm::ConstantDataArray::getString(ctx, rawData, false);
    // RawArray's memory layout is struct {i8* ArrayKlassInfo, i64 length, [? x i8] rawdata}
    std::vector<llvm::Type*> elemTypes{int8PtrType, int64Type, strContent->getType()};
    auto rawArrayType = llvm::StructType::get(ctx, elemTypes);
    auto arrayKlassInfo = GetReadOnlyArrayKlassInfo(cgMod);
    auto rawArrayData = llvm::ConstantStruct::get(rawArrayType,
        {llvm::ConstantExpr::getBitCast(arrayKlassInfo, int8PtrType),
            llvm::ConstantInt::getSigned(int64Type, static_cast<int64_t>(rawData.size())), strContent});

    std::string cjStringDataName = GetCjStringDataLiteralName(rawData);
    auto gvRawData =
        llvm::cast<llvm::GlobalVariable>(cgMod.GetLLVMModule()->getOrInsertGlobal(cjStringDataName, rawArrayType));
    CJC_NULLPTR_CHECK(gvRawData);
    gvRawData->setInitializer(rawArrayData);
    gvRawData->setConstant(true);
    gvRawData->addAttribute(CJSTRING_DATA_ATTR);
    gvRawData->setLinkage(llvm::GlobalValue::PrivateLinkage);

    // 3. Set Initializer for all cj string literal
    auto cjStringType = cgMod.GetCGContext().GetCjStringType();
    auto i8Ptr = llvm::ConstantExpr::getBitCast(gvRawData, int8PtrType);
    auto i8PtrAddr1 = llvm::ConstantExpr::getAddrSpaceCast(i8Ptr, llvm::Type::getInt8PtrTy(ctx, 1u));

    for (const auto& cjStringIter : cjStrings) {
        auto& cjStringName = cjStringIter.first;
        auto& cjStringContent = cjStringIter.second;
        size_t pos = rawData.find(cjStringContent);
        if (!cgMod.GetLLVMModule()->getNamedValue(cjStringName) || pos == std::string::npos) {
            // cjString may have been optimized and deleted.
            continue;
        }

        auto dataStart = llvm::ConstantInt::getSigned(int32Type, static_cast<int32_t>(pos));
        auto strSize = llvm::ConstantInt::getSigned(int32Type, static_cast<int32_t>(cjStringContent.size()));
        // in LLVM IR:
        // cj string = type { i8 addrspace(1)*, i32, i32 }
        auto cjStringInit = llvm::ConstantStruct::get(cjStringType, {i8PtrAddr1, dataStart, strSize});
        auto gv = llvm::cast<llvm::GlobalVariable>(cgMod.GetLLVMModule()->getNamedValue(cjStringName));
        CJC_NULLPTR_CHECK(gv);
        gv->setInitializer(cjStringInit);
    }
}

namespace {
void TraverseAndGenerateCallSetFrom(std::set<llvm::CallGraphNode*>& ret, llvm::CallGraphNode* root)
{
    std::queue<llvm::CallGraphNode*> queue;
    queue.emplace(root);
    do {
        auto node = queue.front();
        queue.pop();
        if (ret.find(node) != ret.end()) {
            continue;
        }
        ret.emplace(node);
        for (auto callee = node->begin(); callee != node->end(); ++callee) {
            auto calleeNode = callee->second;
            if (ret.find(calleeNode) == ret.end()) {
                queue.emplace(calleeNode);
            }
        }
    } while (!queue.empty());
}
} // namespace

void GenerateBinarySectionInfo(const CGModule& cgMod)
{
    if (cgMod.GetCGContext().GetCGPkgContext().IsCGParallelEnabled()) {
        return;
    }
    auto module = cgMod.GetLLVMModule();
    const std::string cjInitAttrStr = "cjinit";
    auto callGraph = llvm::CallGraphWrapperPass();
    callGraph.runOnModule(*module);
    auto globalInitFuncName = cgMod.GetCGContext().GetCHIRPackage().GetPackageInitFunc()->GetIdentifierWithoutPrefix();
    auto pkgInitFunc = module->getFunction(globalInitFuncName);
    CJC_NULLPTR_CHECK(pkgInitFunc);
    auto pkgInitNode = callGraph[pkgInitFunc];
    std::set<llvm::CallGraphNode*> callSet;
    TraverseAndGenerateCallSetFrom(callSet, pkgInitNode);
    if (pkgInitFunc->getSection().empty()) {
        AddFnAttr(pkgInitFunc, llvm::Attribute::get(pkgInitFunc->getContext(), cjInitAttrStr));
    }
    // Add `cjinit` attr to `cj_entry` and `main`
    std::vector<std::string> mainFuncs{CJ_ENTRY_FUNC_NAME, "main"};
    for (auto& f : mainFuncs) {
        if (auto func = module->getFunction(f); func && func->getSection().empty()) {
            func->addFnAttr(llvm::Attribute::get(func->getContext(), cjInitAttrStr));
        }
    }
    // Add `cjinit` attr to `user.main` and functions that are directly called by `user.main`
    if (auto userMainFunc = module->getFunction(USER_MAIN_MANGLED_NAME);
        userMainFunc && userMainFunc->getSection().empty()) {
        userMainFunc->addFnAttr(llvm::Attribute::get(userMainFunc->getContext(), cjInitAttrStr));
        auto userMainNode = callGraph[userMainFunc];
        for (auto callee = userMainNode->begin(); callee != userMainNode->end(); ++callee) {
            if (auto calleeFunc = callee->second->getFunction(); calleeFunc && calleeFunc->getSection().empty()) {
                calleeFunc->addFnAttr(llvm::Attribute::get(calleeFunc->getContext(), cjInitAttrStr));
            }
        }
    }
    for (auto node : callSet) {
        auto func = node->getFunction();
        if (!func) {
            // The callee func is not defined in this module, so it should be ignored.
            continue;
        }
        if (func->getSection().empty()) {
            func->addFnAttr(llvm::Attribute::get(func->getContext(), cjInitAttrStr));
        }
    }
}
} // namespace Cangjie::CodeGen
